package com.bang.study.day09;

import com.bang.study.day07.Map;

import java.util.TreeMap;

/**
 * @Auther: Bang
 * @Date: 2019/9/21 00:12
 * @Description: 基于TreeMap实现hashTable 链地址法解决hash重复
 */
public class HashTable<K, V> implements Map<K, V> {

    private static int uppertol = 10;

    private static int lowerTol = 2;

    private static int initCapacity = 7;

    private TreeMap<K, V>[] hashTable;

    // hashcode % 素数
    private int M;

    private int size;

    public HashTable(int M) {
        this.M = M;
        this.size = 0;
        this.hashTable = new TreeMap[M];
        for (int i = 0; i < M; i++) {
            // 初始化对象
            hashTable[i] = new TreeMap<>();
        }
    }

    public HashTable() {
        this(initCapacity);
    }

    /**
     * 求key的hashcode值
     *
     * @param key
     * @return
     */
    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    public void add(K key, V value) {
        TreeMap<K, V> treeMap = hashTable[hash(key)];
        if (treeMap.containsKey(key)) {
            treeMap.put(key, value);
        } else {
            treeMap.put(key, value);
            size++;
            if (size >= M * uppertol) {
                resize(2 * M);
            }
        }
    }


    public void set(K key, V newValue) {
        TreeMap<K, V> treeMap = hashTable[hash(key)];
        if (!treeMap.containsKey(key)) {
            throw new IllegalArgumentException("KEY IS NOT FOUND");
        }
        treeMap.put(key, newValue);
    }

    @Override
    public V remove(K key) {
        TreeMap<K, V> treeMap = hashTable[hash(key)];
        V ret = null;
        if (treeMap.containsKey(key)) {
            ret = treeMap.remove(key);
            size--;
            if (size <= lowerTol * M && M  > initCapacity) {
                resize(M / 2);
            }
        }
        return ret;
    }

    /**
     * 扩容 缩容
     *
     * @param newM
     */
    private void resize(int newM) {
        TreeMap<K, V>[] newMap = new TreeMap[newM];
        for (int i = 0; i < newM; i++) {
            newMap[i] = new TreeMap<>();

        }
        int oldM = M;
        this.M = newM;
        for (int i = 0; i < oldM; i++) {
            TreeMap<K, V> treeMap = hashTable[i];
            for (K key : treeMap.keySet()) {
                newMap[hash(key)].put(key, treeMap.get(key));
            }
        }
        this.hashTable = newMap;

    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    public boolean contains(K key) {
        return hashTable[hash(key)].containsKey(key);
    }

    @Override
    public V get(K key) {
        return hashTable[hash(key)].get(key);
    }

}
